﻿using System;
using System.Collections.Generic;
using System.Data;
using System.IO;
using System.Linq;
using System.Text;


namespace www.coursera.algo.org.ProblemQuestion._3
{
    class Program
    {
        static void Main(string[] args)
        {

            #region intitilize test cases
            char[] delimiterChars = { ' ', ',', '.', ':', '\t' };
            Dictionary<string, int> expectations = new Dictionary<string, int>()
{
    { "kargerAdj.txt", 3 } ,
    {"adjList01m1.txt", 1},
                 {"adjList02m2.txt", 2},
                 {"adjList03m1.txt", 1},
                 {"adjList04m1.txt", 1},
                 {"adjList05m2.txt", 2},
                 {"adjList06m3.txt", 3},
                 {"adjList07m1.txt", 1},
                 {"adjList08m1.txt", 1},
                 {"adjList09m1.txt", 1},
                 {"adjList10m2.txt", 2},
                 {"n3m3_2.txt", 2},
                 {"n3m5_2.txt", 2},
                 {"n4m5_2.txt", 2},
                 {"n4m6_3.txt", 3},
                 {"n5m5_2.txt", 2},
                 {"n8m14_2.txt", 2},
                 {"test0_m3.txt", 3},
                 {"test0_m5.txt", 5},
                 {"test1.2.txt", 2},
                 {"test1bm3.txt", 3},
                 {"test1_m5.txt", 5},
                 {"test1_m6.txt", 6},
                 {"test2.4.txt", 4},
                 {"test2b2.txt", 2},
                 {"test2_m5.txt", 5},
                 {"test2_m7.txt", 7},
                 {"test3.1.txt", 1},
                 {"test3_m3.txt", 3},
                 {"test4.3.txt", 3},
                 {"test4_m5.txt", 5},
                 {"test5_m4.txt", 4},
                 {"test6_m4.txt", 4},
                 {"test7_m4.txt", 4},
                 {"test8_m3.txt", 3},
                 {"test9_m4.txt", 4} 

};

            #endregion



           
        

        int count = 5000;
            foreach (KeyValuePair<string, int> keyValuePair in expectations)
            {
                int minResult = RunMinCutOnFile(keyValuePair.Key, count);
                Console.ResetColor();
                if (minResult != keyValuePair.Value)
                {
                    Console.ForegroundColor = ConsoleColor.Red;
                }
                else
                {
                    Console.ForegroundColor = ConsoleColor.Green;
                }

                Console.WriteLine("No of cuts for filename {0} is {1} and expected result is {2}", keyValuePair.Key, minResult, keyValuePair.Value);
                
                
            }
            Console.WriteLine("----------Done-------------");
            Console.ReadLine();

          

            

        }



        private static int RunMinCutOnFile(string fileName,int countLimit)
        {
            int minResult = 100;
            char[] delimiterChars = { ' ', ',', '.', ':', '\t' };
            int count = 0;
            while(count<countLimit)
            {
                Graph graph = new Graph();
                using (StreamReader sr = new StreamReader("TestCases\\"+fileName))
                {
                    String line;
                    // Read and display lines from the file until the end of
                    // the file is reached.
                    while ((line = sr.ReadLine()) != null)
                    {
                        if(line.IndexOf("#")<0)
                        {
                            string[] list = line.Split(delimiterChars, StringSplitOptions.RemoveEmptyEntries);
                            Vertex currVertex = new Vertex(list[0]);
                            graph.AddVertex(currVertex);
                            for (int i = 1; i < list.Length; i++)
                            {
                                Vertex edgeVertex = new Vertex(list[i]);
                                graph.AddEdge(currVertex, edgeVertex);
                            }
                            //console.writeLine(line);
                        }
                    }
                }
                ////console.writeLine(graph.Print());
                //Console.ReadLine();
                ////console.writeLine("<---------------------------------Start of new loop------------------------------------->");
                int cuts = graph.FindCuts();
                if(minResult>cuts)
                {
                    minResult = cuts;
                }

                //graph.Edges.Add(new Edge(a,b));
                

                //console.writeLine(graph.Print());

                
                count = count + 1;
            }
            return minResult;
        }
    }

    public class Graph
    {
        private List<Vertex> Vertices;

        private List<Edge> Edges;

        public Graph()
        {
            this.Vertices = new List<Vertex>();
            this.Edges = new List<Edge>();
        }


        public void AddEdge(Vertex currVertex, Vertex edgeVertex)
        {
            
            AddVertex(edgeVertex);
            Edge newEdge = new Edge(currVertex, edgeVertex);
            if (this.Edges.Count <= 0)
            {
                this.Edges.Add(new Edge(currVertex, edgeVertex));

            }
            else if (!this.Edges.Exists(p => p.CompareTo(newEdge) == 0))
            {
                this.Edges.Add(new Edge(currVertex, edgeVertex));
            }
            //this.Edges.Add(new Edge(currVertex, edgeVertex));
            
        }

        public void AddVertex(Vertex currVertex)
        {
            if (this.Vertices.Count<=0)
            {
                this.Vertices.Add(currVertex);
            }
            else if (!this.Vertices.Exists(p => p.CompareTo(currVertex) == 0))
            {

                this.Vertices.Add(currVertex);
            }
            
        }

        public int FindCuts()
        {
            while (this.Vertices.Count>2 )
            {

                int index = (new Random()).Next(0, this.Edges.Count);
                Edge selectedEdge = this.Edges[index];
                this.Merge(selectedEdge);
            }

            return this.Edges.Count;

        }

        private void Merge(Edge selectedEdge)
        {
            this.Vertices.RemoveAll(p => p.CompareTo(selectedEdge.Vertex2)==0);
            ////console.writeLine("mergin edge {0} for a grpah with total edges={1} and vertices ={2}",selectedEdge.Print(),this.Edges.Count,this.Vertices.Count);

            this.Edges.Remove(selectedEdge);

            //Change all edge with vertex2 and change it to vertex1

            this.Edges.FindAll(p => p.Vertex1.CompareTo(selectedEdge.Vertex2)==0).ForEach(
                p => p.Vertex1 = selectedEdge.Vertex1);

            this.Edges.FindAll(p => p.Vertex2.CompareTo(selectedEdge.Vertex2) == 0).ForEach(
                p => p.Vertex2 = selectedEdge.Vertex1);

            //Remove self loops);
            this.Edges.RemoveAll(p => p.Vertex1.CompareTo(p.Vertex2) == 0);

            ////console.writeLine(this.Print());
        }

        public string Print()
        {
            StringBuilder  x  = new StringBuilder();
            x.AppendLine("Edges");
            this.Edges.ForEach(p=>x.AppendLine(p.Print()));

            x.AppendLine("Vertex");
            this.Vertices.ForEach(p=>x.AppendLine(p.Print()));
            return x.ToString();

        }
    }

    public class Edge : IComparable<Edge>

    {

        public Vertex Vertex1; // Vertex one

        public Vertex Vertex2; // Vertex two

        //public float Distance; // DIstance or similar

        //public float Cost; // Cost or multiplier factor

        // Contructor

        public Edge(Vertex Vertex1, Vertex Vertex2)

        {

        this.Vertex1 = Vertex1;

        this.Vertex2 = Vertex2;

        //this.Distance = distance;

        //this.Cost = cost;

        }

        #region Implementation of IComparable<in Edge>

        /// <summary>
        /// Compares the current object with another object of the same type.
        /// </summary>
        /// <returns>
        /// A value that indicates the relative order of the objects being compared. The return value has the following meanings: Value Meaning Less than zero This object is less than the <paramref name="other"/> parameter.Zero This object is equal to <paramref name="other"/>. Greater than zero This object is greater than <paramref name="other"/>. 
        /// </returns>
        /// <param name="other">An object to compare with this object.</param>
        public int CompareTo(Edge other)
        {
            if(this.Vertex1.CompareTo(other.Vertex1)==0)
            {
                return this.Vertex2.CompareTo(other.Vertex2);
            }
            else if (this.Vertex1.CompareTo(other.Vertex2)==0)
            {
                return this.Vertex2.CompareTo(other.Vertex1);
            }
            else
            {
                return 1;
            }
        }

        #endregion

        public string Print()
        {
            return "{"+this.Vertex1.Print()+" , "+this.Vertex2.Print()+"}";
        }
    }

    public class Vertex:IComparable<Vertex> {


        public string id; // Label

        //public float x; // Horizontal location on screen

        //public float y; // Vertical location on screen

        // Construcutor

        public Vertex(string id)

        {

        this.id = id;

        //this.x = x;

        //this.y = y;

        }

        /// <summary>
        /// Compares the current object with another object of the same type.
        /// </summary>
        /// <returns>
        /// A value that indicates the relative order of the objects being compared. The return value has the following meanings: Value Meaning Less than zero This object is less than the <paramref name="other"/> parameter.Zero This object is equal to <paramref name="other"/>. Greater than zero This object is greater than <paramref name="other"/>. 
        /// </returns>
        /// <param name="other">An object to compare with this object.</param>
        public int CompareTo(Vertex other)
        {
            return other.id.CompareTo(this.id);
        }

        public override string ToString()

        {

        //return (id + " – " + x.ToString() + " – " + y.ToString());
            return "";

        }

        public string Print()
        {
            return this.id;
        }
    }
}

